package com.gaogzhen.algorithm.sort;

/**
 * 插入排序
 * 1. 插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的
 * 2. 现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的
 * 3. 按照此法对所有元素进行插入，直到整个序列排为有序的过程
 */

public class Insertion {
    // 排序
    // 单个序列多次比较，一步到位比较实现


    // 内循环中将较大的元素右移而不总是交换2个元素，这样访问数组的次数就能减半
    public static void sortImprove(Comparable[] a) {

        for (int i = 1; i < a.length; i++) {
            // 保存当前元素的值
            Comparable k = a[i];
            for (int j = i; j > 0; j--) {
                // 当前元素逆序和有序元素依次比较
                if (compare(a[j - 1], k)) {
                    // 当前元素小于等于前面元素，把较大的元素右移
                    a[j] = a[j-1];
                    // 如果比较到有序元素最左端，当前元素还是最小的，则吧当前元素放置索引为0的位置，结束内循环
                    if (j == 1) {
                        a[0] = k;
                        break;
                    }
                } else {
                    // 当前元素大于要比较的元素，吧当前元素插入当前位置(之前较大元素已经右移)
                    if (j != i) {
                        a[j] = k;
                    }
                    break;
                }
            }

        }
    }
    // 单个序列多次比较，一步到位比较实现
    public static void sortOneStep(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            int j = i - 1;
            // 查找要插入的位置
            for (; j >= 0; j--) {
                if (!compare(a[j], a[i])) {
                     break;
                }
            }

            if (j != i - 1) {
                // 要插入位置元素依次后移
                Comparable tmp = a[i];
                for (int k = i; k > j + 1; k --) {
                    a[k] = a[k - 1];
                }
                a[j + 1] = tmp;
            }
        }
    }

    // 单个序列逐个比较实现
    public static void sort(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {

            for (int j = i; j > 0; j--) {
                if (compare(a[j - 1], a[j])) {

                    exch(a, j - 1, j);
                } else {
                    break;
                }
            }
        }
    }


    // 2个序列实现
    public static void sort(Comparable[] source, Comparable[] target) {
        target[0] = source[0];
        for (int i = 1; i < source.length; i++) {
            for (int j = 0; j < i; j++) {
                if (compare(target[j], source[i])) {
                    for (int k = i; k > j; k--) {
                        target[k] = target[k - 1];
                    }
                    target[j] = source[i];
                    break;
                }
            }
            if (target[i] == null) {
                target[i] = source[i];
            }
        }

    }


    // 比较a是否大于b
    public static boolean compare(Comparable a, Comparable b) {
        return a.compareTo(b) > 0;
    }

    // 交换元素
    public static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
